1. Field of the Invention
The present invention relates to an information processing device, an information processing method and a program. More particularly, the invention relates to an information processing device, an information processing method and a program for analyzing a three-dimensional space.
2. Description of the Related Art
In an approach, a three-dimensional space is analyzed by capturing the space with a camera and analyzing the captured image. For example, two or more feature points (also called landmarks) are extracted from the captured image and three-dimensional positions of these feature points are estimated.
In this approach, images are captured with a moving camera and loci of feature points included in two or more captured images are analyzed. Thus, three-dimensional positions of the feature points and position and attitude of the camera (own) are estimated (i.e., localized). A neighborhood map (i.e., an environmental map) can be generated (i.e., mapped) using three-dimensional position information about the feature points. These localization of the camera (own) and mapping of the neighborhood map (i.e., the environmental map) are performed at the same time is called simultaneous localization and mapping (SLAM).
An approach for SLAM includes an EKF-based SLAM which employs an Extended Kalman filter (EKF). The EKF-based SLAM is described in, for example, S. Thrun, W. Burgard and D. Fox, “Probabilistic Robotics” The MIT Press, Cambridge, Mass., 2005).
In the EKF-based SLAM, for example, images are successively captured with a moving camera, loci (i.e., tracking information) of feature points included in each of the images are obtained, and then travel distance of the camera and three-dimensional positions of the feature points are estimated simultaneously by a moving stereo method.
The EKF-based SLAM uses “status data” including multidimensional normal distribution data as a probability distribution model including data like position, attitude, speed and angular speed of a camera, and position information about each of the feature points. The “status data” is updated with the Kalman filter or the Extended Kalman filter in order to estimate positions of the feature points and the camera.
The “status data” is constituted by multidimensional normal distribution data which includes a mean vector and a variance-covariance matrix. The mean vector represents position, attitude, speed and angular speed of a camera and position information about each of the feature points. The variance-covariance matrix includes variance of inherent status values, such as position, attitude, speed and angular speed of a camera, and position information about each of the feature points, and covariance which corresponds to combinations of correlation information of different status values from among the status values mentioned above. The data structure will be described in detail with reference to embodiments of the invention.
In the EKF-based SLAM, “status data” is updated using images captured with a camera. Thus, information about the feature points registered in the “status data” but not included in the most recently captured image which is input as an image to be processed is also updated. That is, some feature points included in a preceding input image are not included in the most recently input image. Information about the feature points included in a preceding input image is registered in the “status data.” Thus, information regarding correlation between a “feature point caught by the camera” included in the “status data” and a “feature point not caught by the camera” is also updated with the Kalman filter.
This indicates that a larger area for which a map is to be generated involves a greater number of feature points. If the “status data” includes a large amount of feature point information, updating of the “status data” using the Kalman filter or the Extended Kalman filter involves an increased calculation amount.
As described above, the “status data” includes a variance-covariance matrix, which holds information regarding correlation between each of the feature points and the camera. An increased number of feature points involve an increased size of variance-covariance matrix. A calculation amount in updating the “status data” using the Kalman filter or the Extended Kalman filter increases in an order of O (9n2) with respect to the number n of the feature points. Since data should be updated repeatedly, there is a problem that calculation load and processing time increase excessively for generating a large-sized three-dimensional map with a large number of feature points.